package engine;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import tree.Node;
import tree.Tree;

/*
 *  TODO: SHIT WORKS
 *  
 *  Stuff to improve: Size of the walkmap (shit's too slow yo). Also 
 *  handling for cases in which a path cannot be found.
 */
public class AStar {
	
	private Tree map;
	private Node startNode;
	private Node endNode;
	private List<Node> openList;
	private List<Node> closedList;
	
	public AStar(Tree map, Node startNode, Node endNode) {
		
		this.map = map;
		this.startNode = startNode;
		this.endNode = endNode;
		
		openList = new ArrayList<Node>();
		closedList = new ArrayList<Node>();
	}
	
	public List<Node> runAStar() {
		
		Node currentNode = startNode;
		
		// Add the starting node to the open list
		openList.add(startNode);
		
		// Do this while we haven't found the endNode
		while(!openList.contains(endNode)) {
			
			// FOR TESTING
			startNode.setParent(null);
		
			// if no path can be found
			if(openList.isEmpty()) {
				return null;
			}			
			
			// Calculate F values for all items in the open list
			calculateF();
			
			// Sort the open list (by f value, ascending)
			Collections.sort(openList);
			
			/*
			 *  Our current node is the one with the lowest f score
			 *  (first element in the open list). 
			 *  Move it from the open to the closed list.
			 */
			currentNode = openList.get(0);
			openList.remove(0);
			closedList.add(currentNode);		
			
			// Find the neighbors of the current node
			List<Node> neighbors = map.getNeighborsForNode(currentNode.getX(), currentNode.getY());
			
			// For each neighbor
			for(int i=0; i<neighbors.size(); i++) {
				
				/*
				 *  If the adjacent node is walkable and not already on 
				 *  the closed list
				 */
				if(neighbors.get(i).isWalkable() && !closedList.contains(neighbors.get(i))) {
					
					/*
					 *  If it isn't on the open list, add it
					 *  and make the current node the parent of this one
					 */
					if(!openList.contains(neighbors.get(i))) {
						
						openList.add(neighbors.get(i));
						neighbors.get(i).setParent(currentNode);
						calculateF();
					}
					/*
					 * If it is on the open list, check to see if this path
					 * to that node is better, using G.
					 */
					else {
						/*
						 *  compare current g score to g score if we went through
						 *  currentNode
						 */
						int newScore = 0;
						
						if(neighbors.get(i).getX() == currentNode.getX() ||
								neighbors.get(i).getY() == currentNode.getY()) {
							
							newScore = currentNode.getG()+10;
							
						}
						else {
							newScore = currentNode.getG()+14;
						}

						/*
						 * If the path would be better, change the parent
						 * of this node to the current node
						 */
						if(newScore < neighbors.get(i).getG()) {
							neighbors.get(i).setParent(currentNode);
							calculateF();
							Collections.sort(openList);
	
						}
					}
				}
			}
		}		

		// Reconstruct the path
		Node n = endNode;
		List<Node> path = new ArrayList<Node>();
		
		// If we go up the tree towards the root, we get all nodes in the path
		while(n.getParent() != null) {
			path.add(n);
			n = n.getParent();
		}

		/*
		 *  Since we added them in reverse order, reverse our list to
		 *  get the correct order.
		 */
		Collections.reverse(path);
		return path;
	}
	
	/**
	 * Iterates through the open list and (re-)calculates the f values.
	 */
	private void calculateF() {
				
		for(int i=0; i<openList.size(); i++) {
			
			Node current = openList.get(i);
			
			/* ********************************************************
			 *  Calculate G (distance to starting node)			
			 * ********************************************************
			 *
			 *  If this is the first node in the path, it's the
			 *  starting node, so the distance to itself is 0.
			 */
			if(current.getParent() == null) {
				current.setG(0);
			}
			/*
			 * Else, g is calculated by adding 10 or 14 to the g
			 * score of the parent, depending on whether we are 
			 * orthogonal or horizontal from the parent.
			 */
			else {
				
				/*
				 * This node is orthogonal to the parent if either
				 * the x coordinates are the same or the y coordinates.
				 */				
				if(current.getParent().getX() == current.getX()
						|| current.getParent().getY() == current.getY()) {
					
					current.setG(current.getParent().getG()	+ 10);
				}
				else {
					current.setG(current.getParent().getG() + 14);
				}
			}
			
			/* **************************************************************
			 * Calculate H (estimated distance to the end node)
			 * 
			 * Estimation is number of nodes moved left/right, up/down to
			 * reach the goal * 10 (no diagonal movement)
			 * **************************************************************
			 */
			int count = 0;
			int tempX;
			tempX = current.getX();
			int tempY;
			tempY = current.getY();
			
			// count how many steps are needed to reach the end node
		
			if(tempX > endNode.getX()) {
				while(tempX != endNode.getX()) {
					tempX--;
					count++;
				}
			}
			
			if(tempX < endNode.getX()) {
				while(tempX != endNode.getX()) {
					tempX++;
					count++;
				}
			}
			
			if(tempY > endNode.getY()) {
				while(tempY != endNode.getY()) {
					tempY--;
					count++;
				}
			}
			
			if(tempY < endNode.getY()) {
				while(tempY != endNode.getY()) {
					tempY++;
					count++;
				}
			}
			
			current.setH(count*10);
			
			// Now set the f value
			current.setF(current.getG()+current.getH());	
		}
	}
}
